#ifndef GRAFOIMP_CPP
#define GRAFOIMP_CPP

#include "GrafoImp.h"


//Contructor
template <class V, class A>
GrafoImp<V,A>::GrafoImp(int ( * fHash)(const V &, int), int cantVertices){
	cantVerticesActuales =0;
	fHashV = fHash;
	Vacio(fHashV, cantVertices);
}

template<class V, class A>
GrafoImp<V,A>::~GrafoImp(){
	VerticesHash->~Tabla();

	
}

template<class V, class A>
void GrafoImp<V,A>::Vacio(int ( * fHash)(const V &, int), int cantVertices){
	VerticesHash = new TablaHash<V,int>( fHashV, cantVertices, LAMBDA);
	arrayVertices = Array<V> (cantVertices+1);	
    matrizAdyacencias = Matriz<A>(cantVertices+1);
	for (int i = 1; i < cantVertices+1; i++){
		for (int j = 1; j < cantVertices+1; j++){
            matrizAdyacencias[i][j] = NULL;
		}
    }
}
	
template<class V, class A>
void GrafoImp<V,A>::AgregarVertice(const V& v){
	if(!ExisteVertice(v))
	{		
		cantVerticesActuales++;
		VerticesHash->Insertar(v, cantVerticesActuales);
		arrayVertices[cantVerticesActuales] = v;
	}
}
	
template<class V, class A>
void GrafoImp<V,A>::AgregarArista(const V& v1, const V& v2, const A& a){
	int vO, vD;
	// obtengo la posicion del vertice v1 en la matriz
	vO =VerticesHash->devolverRango(v1);
	// obtengo la posicion del vertice v2 en la matriz
	vD = VerticesHash->devolverRango(v2);
	if(ExisteVertice(v1) && ExisteVertice(v2)&& !ExisteArista(v1, v2))
	{
		matrizAdyacencias[vO][vD]=a;
		matrizAdyacencias[vD][vO]=a;
	}
}

//SELECTORAS
template<class V, class A>
A& GrafoImp<V,A>::obtenerArista(const V& v1, const V& v2){
	int vO, vD;
	// obtengo la posicion del vertice v1 en la matriz
	vO =VerticesHash->devolverRango(v1);
	// obtengo la posicion del vertice v2 en la matriz
	vD = VerticesHash->devolverRango(v2);
	return matrizAdyacencias[vO][vD];
}
	
template<class V, class A>
Puntero<Iterador<V>> GrafoImp<V,A>::obtenerAdyacentes(const V& v){
	Puntero<Lista<V>> lstAdyacentes = new ListaImp<V>;
	// obtengo la posicion del vertice v en la matriz
	int pos = VerticesHash->devolverRango(v);
	// recorro la fila de pos de la matriz
	for(int i =1; i<=cantVerticesActuales;i++){
		A arista = matrizAdyacencias[pos][i];
		if(arista!=NULL){
			V vertice = arrayVertices[i];
			lstAdyacentes->Agregar(vertice);
		}
	}
	Puntero<Iterador<V>> iterador =lstAdyacentes->ObtenerIterador();
	return iterador;
}
	
	//pre: el vertice existe
	//pos: devuelve un puntero a los vertices que son incidentes a v
template<class V, class A>
Puntero<Iterador<V>> GrafoImp<V,A>::obtenerIncidentes(const V& v){
	Puntero<Lista<V>> lstAdyacentes = new ListaImp<V>;
	// obtengo la posicion del vertice v en la matriz
	int pos = VerticesHash->devolverRango(v);
	// recorro la fila de pos de la matriz
	for(int i =1; i<=cantVerticesActuales;i++){
		A arista = matrizAdyacencias[i][pos];
		if(arista!=NULL){
			V vertice = arrayVertices[i];
			lstAdyacentes->Agregar(vertice);
		}
	}
	Puntero<Iterador<V>> iterador =lstAdyacentes->ObtenerIterador();
	return iterador;
}

template<class V, class A>
Puntero<Iterador<A>> GrafoImp<V,A>:: obtenerAristas(){
	Puntero<Lista<A>> aristas = new ListaImp<A>;
	for (int i = 1; i<=cantVerticesActuales; i++){
		for (int j = 1; j <=cantVerticesActuales; j++){
			if (ExisteArista(arrayVertices[i], arrayVertices[j])){
				aristas->Agregar(obtenerArista(arrayVertices[i], arrayVertices[j]));
			}
		}
	}
	return aristas->ObtenerIterador();
}

template<class V, class A>
Puntero<Iterador<V>> GrafoImp<V,A>:: obtenerVertices(){
	Puntero<Lista<V>> vertices = new ListaImp<V>;
	for (int i = 1; i<=cantVerticesActuales; i++){
		vertices->Agregar(arrayVertices[i]);
		
	}
	return vertices->ObtenerIterador();
}


	//PREDICADOS
template<class V, class A>
bool GrafoImp<V,A>::EsVacio(){
	return cantVerticesActuales==0;
}

template<class V, class A>
bool GrafoImp<V,A>::ExisteVertice(const V& v){
	return VerticesHash->EstaDefinida(v);
}

	
//devuelve true si existe el arco formado por los vertices v1 y v2 en el grafo. false en caso contrario
template<class V, class A>
bool GrafoImp<V,A>::ExisteArista(const V& v1, const V& v2) {
	return obtenerArista(v1,v2)!=NULL ;
}

template<class V, class A>
int GrafoImp<V,A>::cantVertices(){
	return cantVerticesActuales;
}

template<class V, class A>
int GrafoImp<V,A>::cantElementos(Puntero<Iterador<V>> it)
{
	int retorno = 0;
	for(it; it->HayElemento(); it->Avanzar()){
		retorno++;
	}
	return retorno;
}

template<class V, class A>
int GrafoImp<V, A>::devolverPosEnTabla(const V& v){
	return VerticesHash->devolverRango(v);
}

template<class V, class A>
V& GrafoImp<V, A>::devolverVerticeEnArray(int pos){
	return arrayVertices[pos];
}

/////////////////////////////////////////////////////////////////////////////////////////////////////



#endif